package sort.advance;

import sort.simple.BubbleSort;

import java.util.Arrays;

/**
 * 希尔排序
 * @author caasi
 * @since 2022-01-04 14:36:58
 */
public class ShellSort {

    public static void main(String[] args) {
        int n = 100000000;
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            int r = (int) (Math.random() * 1000);
            arr[i] = r;
        }
        //int arr[] = new int[]{56,74,34,24,89,112,34,21,12,9};
        //System.out.println(Arrays.toString(arr));
        long start = System.currentTimeMillis();
        ShellSort.sort(arr);
        long end = System.currentTimeMillis();
        System.out.println("耗时：" + (end - start) + "ms");
        //System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr) {
        //偏移量
        int h = 1;
        //选定初始偏移量
        while (h < (arr.length / 2)) h = h * 2 + 1;
        //分组排序 h每次减半 直到h为1
        while (h >= 1) {
            //排序
            //选择待插入的元素
            for (int i = h; i < arr.length; i++) {
                for (int j = i; j >= h; j -= h) {
                    if (arr[j - h] > arr[j]) {
                        int temp = arr[j - h];
                        arr[j - h] = arr[j];
                        arr[j] = temp;
                    } else {
                        break;
                    }
                }
            }
            h = h / 2;
        }
    }
}
